package heap;

import java.util.Arrays;

public class Heap {
    /**
     * 堆的大小
     */
    private int N;
    private int[] pq;

    /**
     * 根据数组创建堆
     * 
     * @param array 按完全二叉树顺序摆放的数组
     */
    public Heap(int[] array) {
        // 初始化
        N = array.length + 1;
        pq = new int[N];
        for (int i = 1; i < N; i++) {
            pq[i] = array[i - 1];
        }
        // 堆有序化
        for (int i = (N - 1) / 2; i >= 1; i--) {
            sink(i);
        }
    }

    /**
     * 交换 i 和 j 位置
     * 
     * @param i
     * @param j
     */
    private void exch(int i, int j) {
        int tmp = pq[i];
        pq[i] = pq[j];
        pq[j] = tmp;
    }

    /**
     * 由下至上的堆的有序化
     * 
     * @param k 打乱有序的节点序号, 该节点的优先级突然上升(或者是在堆底部新加了个元素)
     */
    private void swim(int k) {
        while (k > 1 && pq[k] > pq[k / 2]) {
            exch(k, k / 2);
            k = k / 2;
        }
    }

    /**
     * 由上至下的堆的有序化
     * 
     * @param k 打乱有序的节点序号, 该节点的优先级突然下降(例如将根节点替换为一个较小的节点)
     */
    private void sink(int k) {
        while (k * 2 <= N - 1) {
            int bigger = k * 2;
            // 如果有两个字节点，找到最大的那个
            if (bigger < N - 1 && pq[bigger + 1] > pq[bigger]) {
                bigger = bigger + 1;
            }
            // 和最大字节点比较
            if (pq[k] < pq[bigger]) {
                exch(k, bigger);
                k = bigger;
            } else {
                break;
            }

        }
    }

    /**
     * 在堆的最后插入元素
     * 
     * @param value
     */
    public void insert(int value) {
        // 扩容
        N = N + 1;
        pq = Arrays.copyOf(pq, N);
        pq[N - 1] = value;
        // 堆的有序化
        swim(N - 1);
    }

    /**
     * 删除最大点
     */
    public int deleteMax() {
        // 保存弹出的最大值
        int returnValue = pq[1];
        exch(1, N--);
        // 缩小容量
        System.arraycopy(pq, 0, pq, 0, N - 1);
        sink(1);
        return returnValue;
    }

    /**
     * 堆排序
     */
    public void sort(){
        int n = N;
        while(N > 2){
            exch(1, N-1);
            N--;
            sink(1);
        }
        N = n;
    }

    @Override
    public String toString() {
        return "Heap [N=" + N + ", pq=" + Arrays.toString(pq) + "]";
    }
}